package dipl.visualizer.algorithm;

/// <summary>

import dipl.algorithm.exception.ArgumentException;
import dipl.algorithm.math.curve.BezierCurve;
import dipl.algorithm.math.geometry.ConvexHull2d;
import dipl.algorithm.math.geometry.op.BoundingWedge2dOps;
import dipl.algorithm.math.geometry.op.ConvexPolygons2d;
import dipl.algorithm.math.primitive.Interval1d;
import dipl.algorithm.math.primitive.Point2d;
import dipl.algorithm.math.utility.FPMath;
import dipl.algorithm.math.primitive.Tuple2;
import dipl.algorithm.math.fp.primitive.Point2df;
import dipl.algorithm.exception.ArgumentNullException;
import dipl.algorithm.impl.Intersection;
import dipl.algorithm.impl.IntersectionType;
import dipl.algorithm.impl.Parameters;
import dipl.algorithm.math.geometry.BoundingWedge2d;
import dipl.algorithm.math.geometry.op.Point2dSetOps;
import dipl.algorithm.statistics.Statistics;
import dipl.visualizer.ui.ShapeViewer;
import dipl.visualizer.graphics.ColorOps;
import dipl.visualizer.graphics.shape.BezierCurveShape;
import dipl.visualizer.graphics.shape.BoundingWedge2dShape;
import dipl.visualizer.graphics.shape.IShape;
import dipl.visualizer.graphics.shape.Polygon2dShape;
import dipl.algorithm.utility.data.RedBlackTree;
import dipl.algorithm.utility.data.comparator.IntervalComparator;
import dipl.algorithm.yap.YapUtilities;
import java.awt.Color;
import java.awt.Font;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
import javax.swing.DefaultListModel;
import javax.swing.JTextArea;
import org.apfloat.Apfloat;

/**
 * The stepwise subdivision algorithm
 */
public class ScmpAlgorithmBezierStepwise {
	
	//
	// TYPES
	//
	
	/**
	 * Represents one curve segment in the subdivision tree.
	 * Along with the curve segment its convex hull and other data
	 * required to determine whether curve segments cross is stored.
	 */
	public class CurveSegment {

		public CurveSegment( BezierCurve curve, BezierCurveShape shape_curve ) {
			InitializeMembers();
			this.curve = curve;
			this.shape_curve = shape_curve;
			this.name = shape_curve != null ? shape_curve.Name() : null;
			this.shape_color = shape_curve != null ? shape_curve.Color() : null;
			this.domain = curve != null ? curve.Domain() : new Interval1d();
		}

		public CurveSegment( String name ) {
			InitializeMembers();
			this.name = name;
		}

		/**
		 * Constructs curve segment which is the union of given two sibling segments
		 * @param name
		 * @param unionSegL left one of sibling segments
		 * @param unionSegR right one of sibling segments
		 */
		public CurveSegment( String name, CurveSegment unionSegL, CurveSegment unionSegR ) {
			InitializeMembers();
			this.name = name;
			this.isUnion = true;
			this.unionSegL = unionSegL;
			this.unionSegR = unionSegR;
		}

		public CurveSegment(
			BezierCurve curve, BezierCurveShape shape_curve,
			ConvexHull2d hull, Polygon2dShape shape_hull
		) {
			InitializeMembers();
			this.curve = curve;
			this.shape_curve = shape_curve;
			this.name = shape_curve != null ? shape_curve.Name() : null;
			this.shape_color = shape_curve != null ? shape_curve.Color() : null;
			this.domain = curve != null ? curve.Domain() : new Interval1d();
			this.shape_hull = shape_hull;
			this.hull = hull;
		}

		public CurveSegment(
			BezierCurve curve, BezierCurveShape shape_curve,
			ConvexHull2d hull, Polygon2dShape shape_hull,
			BoundingWedge2d wedge, BoundingWedge2dShape shape_wedge
		) {
			InitializeMembers();
			this.shape_curve = shape_curve;
			this.curve = curve;
			this.name = shape_curve != null ? shape_curve.Name() : null;
			this.shape_color = shape_curve != null ? shape_curve.Color() : null;
			this.domain = curve != null ? curve.Domain() : new Interval1d();
			this.shape_hull = shape_hull;
			this.hull = hull;
			this.shape_wedge = shape_wedge;
			this.wedge = wedge;
		}

		/** @return count of segments already checked against this segment */
		public int CountCheckedSegments() {
			return checkedIntervals.count();
		}

		/** @return whether or not this segment was constructed as the union of two other segments */
		public boolean IsUnion() {
			return isUnion;
		}

		/** @return left segment of segments from which this was constructed */
		public CurveSegment UnionSegL() {
			return unionSegL;
		}

		/** @return right segment of segments from which this was constructed */
		public CurveSegment UnionSegR() {
			return unionSegR;
		}

		/**
		 * Adds given segment interval to list of intervals
		 * which have already been checked against this one by the algorithm.
		 * We store only intervals here because in the algorithm the curve segments
		 * are not always available (and must be constructed, which is expensive).
		 * @param o
		 */
		public void AddChecked( Interval1d o ) {
			checkedIntervals.insertKey( o );
		}

		/**
		 * @param o
		 * @return whether curve of given segment o is identical to this segment's curve.
		 * If either one of given segment is <code>null</code>, <code>false</code> is returned
		 */
		public boolean CurvesIdentical( CurveSegment o ) {
			if( this.curve == null || o.curve == null )
				return false;
			return this.curve.Equals( o.curve );
		}

		/**
		 * @param o
		 * @return whether segment pair formed by this segment and given one has already
		 * been considered by the algorithm.
		 */
		public boolean IsAlreadyChecked( Interval1d o ) {
			return (checkedIntervals.search( o ) != null);
		}

		/**
		 * @return whether this curve segment is degenerated to one single point.
		 */
		public boolean IsOnePoint() {
			if( curve == null )
				return false;
			return curve.IsDegenerated();
		}

		@Override
		public String toString() {
			String s = "[Name: \""+name+"\"";
			s += ", t: "+domain.L().doubleValue();
			s += ", h: "+domain.Length().doubleValue()+"]";
			return s;
		}

		private void InitializeMembers() {
			this.shape_curve = null;
			this.shape_hull = null;
			this.shape_wedge = null;
			this.curve = null;
			this.hull = null;
			this.wedge = null;
			this.name = null;
			this.domain = new Interval1d();
			this.comp = new IntervalComparator();
			this.checkedIntervals = new RedBlackTree<Interval1d, IntervalComparator>( comp );
			this.isUnion = false;
			this.unionSegL = null;
			this.unionSegR = null;
			this.shape_color = null;
		}

		/** name of curve segment */
		public String name;
		/** parameter domain of curve segment */
		public Interval1d domain;
		/** the curve segment */
		public BezierCurve curve;
		/** segment shape */
		public BezierCurveShape shape_curve;
		/** base color of shapes */
		public Color shape_color;
		/** Convex hull of segment */
		public ConvexHull2d hull;
		/** Shape of convex hull */
		public Polygon2dShape shape_hull;
		/** bounding wedge of curve */
		public BoundingWedge2d wedge;
		/** shape of bounding wedge */
		public BoundingWedge2dShape shape_wedge;
		/** tree containing domains of curve segments which where already checked against this segment */
		private RedBlackTree<Interval1d, IntervalComparator> checkedIntervals;
		/** interval comparator */
		private IntervalComparator comp;
		/** whether or not this segment was constructed by two others */
		private boolean isUnion;
		/** one of the segmetns from which this segment was constructed */
		private CurveSegment unionSegL;
		/** one of the segments from which this segment was constructed */
		private CurveSegment unionSegR;
	};

	/** Represents a node in the subdivision tree for one input curve in the stepwise algorithm */
	protected class SubdivisionNode {

		public SubdivisionNode( CurveSegment seg, SubdivisionNode parent, SubdivisionNode left, SubdivisionNode right ) {
			this.seg = seg;
			this.parent = parent;
			this.left = left;
			this.right = right;
			this.segSP1 = null;
			this.segSP2 = null;
			this.depth = 0;
		}

		/** curve segment of this node */
		public CurveSegment seg;
		/** supercomposition curve segment [t-h,t+h] */
		public CurveSegment segSP1;
		/** supercomposition curve seg [t,t+2h] */
		public CurveSegment segSP2;
		/** parent node */
		public SubdivisionNode parent;
		/** left child */
		public SubdivisionNode left;
		/** right child */
		public SubdivisionNode right;
		/** Depth of node in subdivision tree. Depth 0 means root. */
		public int depth;
	};

	/** States of stepwise algorithm */
	public enum State {

		/** start of algorithm */
		Starting( "Starting" ),
		/** aquire next semgent pair from stack */
		AquireNextPair( "Aquire next curve segment pair" ),
		/** sudivide larger segment of (f,g) */
		SupdivideLargerCurve( "Subdivide larger curve" ),
		/** algorithm finished */
		Finished( "Finished" ),
		/** calculate superposition semgents of current pair */
		CalcSuperpositionData( "Calculate superposition data of current segment pair" ),
		/** check for hull intersection of segment pair */
		CheckPairHullIntersection( "Check whether convex hulls intersect" ),
		/** check for crossing of segment pair */
		CheckPairCrossing( "Check for crossing" ),
		/** check for intersection of bounding wedges */
		CheckPairBoundingWedgeIntersect( "Check for bounding wedge intersection" );

		State( String desc ) {
			this.desc = desc;
		}

		public String Desc() {
			return desc;
		}

		protected String desc;
	};

	//
	// CONSTRUCTOR METHODS
	//

	/**
	 *
	 * @param shapes
	 * @param stackList
	 * @param messageBox
	 */
	public ScmpAlgorithmBezierStepwise( ShapeViewer shapes, DefaultListModel stackList, JTextArea messageBox ) {
		InitializeMembers();

		this.shapeViewer = shapes;
		this.shapeViewer.SetDisplayNames( true );
		this.stackList = stackList;
		this.messageBox = messageBox;
		this.defFont = this.shapeViewer.getFont();
		this.shape_color_f = Color.green;
		this.shape_color_g = Color.blue;
	}

	public ScmpAlgorithmBezierStepwise() {
		InitializeMembers();
	}

	//
	// PUBLIC METHODS
	//

	/**
	 * Proceeds the algorithm from the current to the next state.
	 * @throws Exception
	 */
	public void Proceed() throws Exception {
		if( currentState == State.Finished )
			throw new Exception( "Algorithm has already finished." );

		currentState = nextState;
		switch( currentState ) {

			case Finished:

				statistics.endPrecision = fpMath.Precision();
				nextState = State.Finished;
				PrintMsgLine( "\n=====================\nFinished\n=====================\nResults:" );
				PrintMsgLine( "Found "+macroPairs.size()+" macro pair(s)." );
				PrintMsgLine( "Found "+microPairs.size()+" micro pair(s)." );
				// collect intersections found
				for( Tuple2<Interval1d,Interval1d> p : macroPairs ) {
					AddIntersection( p.fst, p.snd, IntersectionType.Unique );
				}
				for( Tuple2<Interval1d,Interval1d> p : microPairs ) {
					AddIntersection( p.fst, p.snd, IntersectionType.Micro );
				}
				if( intersections.size() == 0 ) {
					PrintMsgLine( "No intersections." );
				}
				else {
					for( Intersection i : intersections ) {
						PrintMsgLine( i.toString() );
					}
				}
				// statistics
				if( (parameters & Parameters.COLLECT_DATA) != 0 ) {
					statistics.subdivisionDepth_f = maxDepth_f;
					statistics.subdivisionDepth_g = maxDepth_g;
					statistics.endPrecision = currentPrecision;
					CalculateSubdivsionTreeMeans();
				}
				PrintMsgLine( "Statistics:\n"+statistics.toString() );
				break;

			case AquireNextPair:
				if( this.shapeViewer != null ) {
					DestroyShapes( State.CheckPairHullIntersection );
					DestroyShapes( State.CheckPairCrossing );
					DestroyShapes( State.CheckPairBoundingWedgeIntersect );
					DestroyShapes( State.AquireNextPair );
				}
				if( stack.size() == 0 ) {
					nextState = State.Finished;
					break;
				}
				if( (parameters & Parameters.SUPERCOMPOSITION) != 0 ) {
					spSegPairs2Check.clear();
					segPair = null;
				}
				cand = stack.pop();
				PrintMsgLine();
				PrintMsgLine( "Aquired segment pair { "+cand.fst.seg.name+", "+cand.snd.seg.name+" }." );
				if( stackList != null )
					stackList.remove( 0 );

				ConstructConvexHull( cand.fst.seg );
				ConstructConvexHull( cand.snd.seg );
				PrintMsg( "Calculate diameter..." );
				size_f = ConvexPolygons2d.CalculateDiameter( fpMath, cand.fst.seg.hull.Vertices(), true );
				size_g = ConvexPolygons2d.CalculateDiameter( fpMath, cand.snd.seg.hull.Vertices(), true );
				PrintMsgLine( "done." );

				// possible intersection because at least one segment is too small?
				if( (parameters & Parameters.BOUNDS_YAP) == 0 ) {
					if( size_f.compareTo( squareTreshold ) < 0 && size_g.compareTo( squareTreshold ) < 0 ) {
						AddIntersection( cand.fst.seg.domain, cand.snd.seg.domain, IntersectionType.Possible );
						PrintMsg( "\n--> Curves are too small. Possible intersection of "+NameOfSegPair( cand.fst.seg, cand.snd.seg )+"\n" );
						nextState = State.AquireNextPair;
						break;
					}
				}
				else {
					if( size_f.compareTo( deltaYap ) < 0 && size_g.compareTo( deltaYap ) < 0 ) {
						AddMicroPair( cand.fst.seg.domain, cand.snd.seg.domain );
						PrintMsg( "\n--> Curves are smaller than Yap bounds!. Micro pair "+NameOfSegPair( cand.fst.seg, cand.snd.seg )+" found.\n" );
						nextState = State.AquireNextPair;
						break;
					}
				}

				segPair = new Tuple2<CurveSegment, CurveSegment>( cand.fst.seg, cand.snd.seg );

				if( this.shapeViewer != null ) {
					CreateShapes( State.AquireNextPair );
				}
				if( (parameters & Parameters.SUPERCOMPOSITION) != 0 )
					nextState = State.CalcSuperpositionData;
				else
					nextState = State.CheckPairHullIntersection;
				break;

			case SupdivideLargerCurve:
				PrintMsgLine( "Subdividing:" );
				// subdivide larger curve
				if( size_f.compareTo( size_g ) > 0 ) {
					// already subdivided?
					if( cand.fst.left != null ) {
						PrintMsgLine( cand.fst.seg.name+" is already subdivided." );
					}
					else {
						SubdivideNode( cand.fst, true );
						PrintMsgLine( "Subdivided curve "+cand.fst.seg.name+"." );
					}
					stack.push( new Tuple2<SubdivisionNode,SubdivisionNode>( cand.fst.left, cand.snd ) );
					stack.push( new Tuple2<SubdivisionNode,SubdivisionNode>( cand.fst.right, cand.snd ) );
					if( stackList != null ) {
						stackList.add( 0, "{"+cand.fst.left.seg.name+", "+cand.snd.seg.name+"}" );
						stackList.add( 0, "{"+cand.fst.right.seg.name+", "+cand.snd.seg.name+"}" );
					}
				}
				else {
					// already partitioned?
					if( cand.snd.left != null ) {
						PrintMsgLine( cand.snd.seg.name+" is already subdivided." );
					}
					else {
						SubdivideNode( cand.snd, false );
						PrintMsgLine( "Subdivided curve "+cand.snd.seg.name+"." );
					}
					stack.push( new Tuple2<SubdivisionNode,SubdivisionNode>( cand.fst, cand.snd.left ) );
					stack.push( new Tuple2<SubdivisionNode,SubdivisionNode>( cand.fst, cand.snd.right ) );
					if( stackList != null ) {
						stackList.add( 0, "{"+cand.fst.seg.name+", "+cand.snd.left.seg.name+"}" );
						stackList.add( 0, "{"+cand.fst.seg.name+", "+cand.snd.right.seg.name+"}" );
					}
				}
				nextState = State.AquireNextPair;
				break;

			case CalcSuperpositionData:

				// with each pair we also aquire the superpositioned curve segments
				oneSCMPPairDisjoint = false;
        CalculateSPSegments();
				// got superpositioned segments
				// no create supercomposition segment pairs (maximal 9 pairs are created)
				// depending on whether they where already considered
				AddSupercompositionPair( cand.fst.segSP1, cand.snd.seg		 ); // (f[t-h,t+h],g)
				AddSupercompositionPair( cand.fst.segSP2, cand.snd.seg		 ); // (f[t,t+2h], g)
				AddSupercompositionPair( cand.fst.segSP2, cand.snd.segSP2 ); // (f[t,t+2h], g[t,t+2h])
				AddSupercompositionPair( cand.fst.segSP2, cand.snd.segSP1 ); // (f[t,t+2h], g[t-h,t+h])
				AddSupercompositionPair( cand.fst.seg,    cand.snd.segSP1 ); // (f,         g[t-h,t+h])
				AddSupercompositionPair( cand.fst.seg,    cand.snd.segSP2 ); // (f,         g[t,t+2h])
				AddSupercompositionPair( cand.fst.segSP1, cand.snd.segSP2 ); // (f[t-h,t+h],g[t,t+2h])
				AddSupercompositionPair( cand.fst.segSP1, cand.snd.segSP1 ); // (f[t-h,t+h],g[t-h,t+h])
				// original pair
				AddSupercompositionPair( cand.fst.seg,    cand.snd.seg ); // finally (f,g)
        nextState = State.CheckPairHullIntersection;
				break;

			case CheckPairHullIntersection:

				if( this.shapeViewer != null ) {
					DestroyShapes( State.AquireNextPair );
					DestroyShapes( State.CheckPairCrossing );
					DestroyShapes( State.CheckPairBoundingWedgeIntersect );
					DestroyShapes( State.CheckPairHullIntersection );
				}

				if( (parameters & Parameters.SUPERCOMPOSITION) != 0 ) {
          segPair = spSegPairs2Check.removeLast();
				}
					
				PrintMsgLine( " --> Checking pair "+NameOfSegPair( segPair.fst, segPair.snd ) );

				// construct hull of segments (if not exist)
				ConstructConvexHull( segPair.fst );
				ConstructConvexHull( segPair.snd );
				if( this.shapeViewer != null ) {
					CreateShapes( State.CheckPairHullIntersection );
				}
				if( ConvexPolygons2d.Intersect( fpMath, segPair.fst.hull.Vertices(), segPair.snd.hull.Vertices() ) ) {
					PrintMsgLine( "Convex hulls do intersect!" );
					nextState = State.CheckPairCrossing;
				}
				else {
					PrintMsgLine( "Convex hulls do not intersect!" );
          if( (parameters & Parameters.SUPERCOMPOSITION) != 0 ) {
            oneSCMPPairDisjoint = true;
          }
          nextState = State.AquireNextPair;
				}
				break;

			case CheckPairCrossing:

				if( ConvexPolygons2d.Crossing( segPair.fst.hull, segPair.snd.hull ) ) {
					PrintMsgLine( "Pair crossing." );
					nextState = State.CheckPairBoundingWedgeIntersect;
				}
				else {
					PrintMsgLine( "Pair not crossing." );
          if( (parameters & Parameters.SUPERCOMPOSITION) == 0 || spSegPairs2Check.size() == 0 )
            nextState = State.SupdivideLargerCurve;
          else
            nextState = State.CheckPairHullIntersection;
				}
				break;

			case CheckPairBoundingWedgeIntersect:
				// construct wedges
				ConstructBoundingWedge( segPair.fst );
				ConstructBoundingWedge( segPair.snd );
				if( this.shapeViewer != null ) {
					DestroyShapes( State.CheckPairCrossing );
					CreateShapes( State.CheckPairBoundingWedgeIntersect );
				}
				if( segPair.fst.wedge != null && segPair.snd.wedge != null ) {
 				if( !BoundingWedge2dOps.Overlap( fpMath, segPair.fst.wedge, segPair.snd.wedge ) ) {
						PrintMsgLine();
            PrintMsgLine( "--> Bounding wedges are disjoint. Unique intersection of "+NameOfSegPair( segPair.fst, segPair.snd )+"." );
						PrintMsgLine( "--> Add to macro pairs." );
						AddMacroPair( segPair.fst.domain, segPair.snd.domain );
						nextState = State.AquireNextPair;
						break;
					}
					else {
						PrintMsgLine( "Bounding wedges intersect!" );
					}
				}
				if( (parameters & Parameters.SUPERCOMPOSITION) == 0 || spSegPairs2Check.size() == 0 )
					nextState = State.SupdivideLargerCurve;
				else
					nextState = State.CheckPairHullIntersection;
				break;
		}
	}

	/**
	 * Starts algorithm
	 * @param f
	 * @param g
	 * @param parameters bit-field of parameters controlling algorithm behaviour
	 * @param treshold
	 * @param L K-bit float bits (in case of yap is enabled)
	 * @throws ArgumentNullException
	 */
	public void Start( 
					BezierCurve f,
					BezierCurve g,
					int parameters,
					Apfloat treshold,
					int L ) throws ArgumentNullException
	{
		if( f == null || g == null )
			throw new ArgumentNullException( "f and g must not be null." );
		this.f = f;
		this.g = g;
		this.treshold = treshold;
		this.parameters = parameters;
		this.L = L;
		ResetMembers();
	}

	//
	// PROPERTIES
	//

	/**
	 * @return whether algorithm has finished (is in final state)
	 */
	public boolean Finished() {
		return currentState == State.Finished;
	}

	/**
	 * @return string representation of current state
	 */
	public String CurrentStateString() {
		return currentState.Desc();
	}

	/**
	 * @return intersections found during last algorithm run.
	 */
	public Iterator<Intersection> Intersections() {
		return intersections.iterator();
	}

	/**
	 * @return object doing fixed precision calculation
	 */
	public FPMath FPMath() {
		return this.fpMath;
	}

	/**
	 *
	 * @return string representation of next state
	 */
	public String NextStateString() {
		return nextState.Desc();
	}

	/**
	 * @return object containing collected statistical information
	 */
	public Statistics Statistics() {
		return statistics;
	}
	//
	// AUXILLIARY METHODS
	//

	/**
	 * Adds given intersection to intersection list.
	 * @param f subinterval of first input curve
	 * @param g subinterval of second input curve
	 * @param type
	 */
	protected void AddIntersection( Interval1d f, Interval1d g, IntersectionType type ) {
		this.intersections.addLast(
			new Intersection( new Interval1d( f ), new Interval1d( g ), type ) );
	}

	/**
	 * Adds pair to macro pair list,
	 * if a pair containing this pair's intervals is not already contained.
	 * @param f first segment interval
	 * @param g second segment interval
	 */
	protected void AddMacroPair( Interval1d f, Interval1d g ) {
		if( (parameters & Parameters.SUPERCOMPOSITION) != 0 && macroPairs.size() > 0 ) {
			for( Tuple2<Interval1d,Interval1d> p : this.macroPairs ) {
				if( p.fst.ProperlyIntersects( f ) &&
						p.snd.ProperlyIntersects( g ) ) {
					PrintMsgLine( "--> Macro pair was already found!" );
					return;
				}
			}
		}
		this.macroPairs.addLast( new Tuple2<Interval1d,Interval1d>( f, g ) );
	}

	/**
	 * Adds pair to micro pair list,
	 * if a pair containing this pair's intervals is not already contained.
	 * @param f first segment interval
	 * @param g second segment interval
	 */
	protected void AddMicroPair( Interval1d f, Interval1d g ) {
		if( (parameters & Parameters.SUPERCOMPOSITION) != 0 && microPairs.size() > 0 ) {
			for( Tuple2<Interval1d,Interval1d> p : this.microPairs ) {
				if( p.fst.ProperlyIntersects( f ) &&
						p.snd.ProperlyIntersects( g ) ) {
					PrintMsgLine( "--> Micro pair was already found!" );
					return;
				}
			}
		}
		this.microPairs.addLast( new Tuple2<Interval1d,Interval1d>( f, g ) );
	}

	/**
		* Trys to add supercomposition candidate pair formed by given two curve segments.
		* If the pair is created it is added to sp-pair list for checking.
		* The creation fails if either one of given segments is <code>null</code> or
		* given pair has already been checked.
		* @param f
		* @param g
	 */
	protected void AddSupercompositionPair( CurveSegment f, CurveSegment g ) {
		if( f == null || g == null )
			return;
		if( !IsSegmentPairAlreadyChecked( f, g ) ) {
			// prevent this pair from being checked twice!
			f.AddChecked( g.domain );
			g.AddChecked( f.domain );

			spSegPairs2Check.addFirst( new Tuple2<CurveSegment,CurveSegment>( f, g ) );
			PrintMsgLine( "Sp-pair "+NameOfSegPair( f, g )+" added!" );
		}
		else {
			PrintMsgLine( "Sp-pair "+NameOfSegPair( f, g )+" has already been checked!" );
		}
	}

	/**
	 * Calculates supercomposition segments of given subdivision node (using extrapolation) if they
	 * don't already exist.
	 * @param n
	 * @param initialDomain
	 */
	protected void CalculateSPSegmentsExtrapolated( SubdivisionNode n, Interval1d initialDomain ) throws ArgumentException {
		if( n.parent != null ) { // if parent is null then we are at the root
			if( n.parent.right == n ) { // we are right child
				if( n.segSP1 == null ) { // -> parent is first sp-segment
					n.segSP1 = n.parent.seg;
					PrintMsgLine( "supercomposition-segment: "+n.seg.name+"[t-h,t+h] is parent ("+n.parent.seg.name+")" );
				}
				if( n.segSP2 == null ) { // -> extrapolate second sp-segment if its contained in initial domain
					Interval1d dom = new Interval1d( n.seg.domain ); // domain of curve segment
					if( initialDomain.ContainsValue( fpMath.m.add( dom.U(), dom.Length() ) ) ) {
						dom.SetBoundsUnsafe( dom.L(), fpMath.m.add( dom.U(), dom.Length() ) );
						String name = n.seg.name+dom.toString();
						BezierCurve curve = n.seg.curve.ChangeDomain( fpMath, dom );
						BezierCurveShape curveShape = null;
						if( this.shapeViewer != null ) {
							curveShape = new BezierCurveShape( fpMath, name, curve , 64, n.seg.shape_curve.Color(), defFont, false );
						}
						n.segSP2 = new CurveSegment( curve, curveShape );
						PrintMsgLine( "supercomposition-segment: "+name+" was extrapolated." );
					}
				}
			}
			else { // we are left child
				if( n.segSP1 == null ) { // -> extrapolate first sp-segment if its contained in initial domain
					Interval1d dom = new Interval1d( n.seg.domain ); // domain of curve segment
					if( initialDomain.ContainsValue( fpMath.m.subtract( dom.L(), dom.Length() ) ) ) {
						dom.SetBoundsUnsafe( fpMath.m.subtract( dom.L(), dom.Length() ), dom.U() );
						String name = n.seg.name+dom.toString();
						BezierCurve curve = n.seg.curve.ChangeDomain( fpMath, dom );
						BezierCurveShape curveShape = null;
						if( this.shapeViewer != null ) {
							curveShape = new BezierCurveShape( fpMath, name, curve, 64, n.seg.shape_curve.Color(), defFont, false );
						}
						n.segSP1 = new CurveSegment( curve, curveShape );
						PrintMsgLine( "supercomposition-segment: "+name+" was extrapolated." );
					}
				}
				if( n.segSP2 == null ) { // -> second sp-segment is parent
					n.segSP2 = n.parent.seg;
					PrintMsgLine( "supercomposition-segment: "+n.seg.name+"[t,t+2h] is parent ("+n.parent.seg.name+")" );
				}
			}
		}
	}

	/**
	 * Calculates supercomposition curve segments of given subdivision node n (without using
	 * extrapolation) if they don't already exist
	 * @param n
	 * @param origCurve
	 */
	protected void CalculateSPSegmentsNotExtrapolated( SubdivisionNode n, BezierCurve origCurve ) {
		if( n.parent != null ) {
			// now aquire and construct supercomposition data
			if( n.parent.right == n ) {
				if( n.segSP1 == null ) {
					n.segSP1 = n.parent.seg;
					PrintMsgLine( "supercomposition-segment: "+n.seg.name+"[t-h,t+h] is parent ("+n.parent.seg.name+")" );
				}
				if( n.segSP2 == null ) {
					SubdivisionNode sibling = GetOrCreateRightSibling( n, origCurve.Domain(), origCurve == this.f );
					if( sibling != null ) {
						Interval1d dom = new Interval1d( n.seg.domain.L(), sibling.seg.domain.U() );
						n.segSP2 = new CurveSegment( n.seg.name+dom.toString(), n.seg, sibling.seg );
						n.segSP2.domain = dom;
						if( this.shapeViewer != null ) {
							n.segSP2.shape_color = origCurve == this.f ? shape_color_f : shape_color_g;
						}
						// we store superpositioned segment in sibling found so that
						// it doesn't have to be constructed when sibling is to be superpositioned
						sibling.segSP1 = n.segSP2;
						PrintMsgLine( "supercomposition-segment: "+n.segSP2.name+" was constructed with right sibling "+sibling.seg.name );
					}
				}
			}
			else {
				if( n.segSP1 == null ) {
					SubdivisionNode sibling = GetOrCreateLeftSibling( n, origCurve.Domain(), origCurve == this.f );
					if( sibling != null ) {
						Interval1d dom = new Interval1d( sibling.seg.domain.L(), n.seg.domain.U() );
						n.segSP1 = new CurveSegment( n.seg.name+dom.toString(), sibling.seg, n.seg );
						n.segSP1.domain = dom;
						if( this.shapeViewer != null ) {
							n.segSP1.shape_color = origCurve == this.f ? shape_color_f : shape_color_g;
						}
						// we store superpositioned hull in  sibling found so that
						// it don't have to be constructed when sibling is to be superpositioned
						sibling.segSP2 = n.segSP1;
						PrintMsgLine( "supercomposition-segment: "+n.segSP1.name+" was constructed with left sibling "+sibling.seg.name );
					}
				}
				if( n.segSP2 == null ) {
					n.segSP2 = n.parent.seg;
					PrintMsgLine( "supercomposition-segment: "+n.seg.name+"[t,t+2h] is parent ("+n.parent.seg.name+")" );
				}
			}
		}
	}

	/**
	 * Calculates supercomposition curve segments of current curve segment pair
	 * under consideration.
	 */
	protected void CalculateSPSegments() throws ArgumentException {
		// first node:
		if( f.CanBeExtrapolated() ) {
			// case 1: curve can be extrapolated
			CalculateSPSegmentsExtrapolated( cand.fst, f.Domain() );
		}
		else {
			// case 2: curve cannot be extrapolated
			CalculateSPSegmentsNotExtrapolated( cand.fst, f );
		}
		// second node
		// first node:
		if( g.CanBeExtrapolated() ) {
			// case 1: curve can be extrapolated
			CalculateSPSegmentsExtrapolated( cand.snd, g.Domain() );
		}
		else {
			// case 2: curve cannot be extrapolated
			CalculateSPSegmentsNotExtrapolated( cand.snd, g );
		}
	}

	/**
	 * Returns the convex hull from the union of control polygons of given two given sibling bezier curve
	 * segments c1 and c2.
	 * It is important to note that resulting polygon will automtically contain the indices of first
	 * control point of c1 and last control point of c2 on the hull if they are contained in hull's vertices.
	 * This is possible because of end-point properties of bezier-curves.
	 * Those indices are most important to determine whether convex hulls of curves are "crossing" later on.
	 * @param s1
	 * @param s2
	 * @return
	 */
	protected ConvexHull2d CombineSegmentHulls( CurveSegment s1, CurveSegment s2 ) {
		ConvexHull2d res = new ConvexHull2d( fpMath, Point2dSetOps.Concat2( s1.hull.Vertices(), s2.hull.Vertices() ) );
		// find end-point vertices
		res.SetFirstPointsetIndex( -1 );
		res.SetLastPointsetIndex( -1 );
		Point2d[] resVert = res.Vertices();
		Point2d p10 = s1.hull.Pointset()[0];
		Point2d p2n = s2.hull.Pointset()[s2.hull.Pointset().length-1];
		for( int i = 0; i < resVert.length; i++ ) {
			if( resVert[i] == p10 ) {
				res.SetFirstPointsetIndex( i );
			}
			if( resVert[i] == p2n ) {
				res.SetLastPointsetIndex( i );
			}
		}
		return res;
	}

	protected void ConstructConvexHull( CurveSegment seg ) throws ArgumentException {
		if( seg.hull != null ) {
			return;
		}
		if( seg.IsUnion() ) {
			// combine hulls
			ConstructConvexHull( seg.UnionSegL() );
			ConstructConvexHull( seg.UnionSegR() );
			seg.hull = CombineSegmentHulls( seg.UnionSegL(), seg.UnionSegR() );
		}
		else {
			seg.hull = new ConvexHull2d( fpMath, seg.curve.Controls() );
		}
		if( this.shapeViewer != null ) {
			seg.shape_hull = new Polygon2dShape( "h_"+seg.name, seg.hull.Vertices(), seg.shape_color );
		}
	}

	/**
	 * Trys to construct bounding wedge for given curve segment from its tangent cone.
	   No wedge is constructed if it is already constructed.
	 *
	 * WARNING: It is assumed that given curve segment contains an actual curve object!
	 * Only segments obtained from subdivision have this property!
	 * @param seg
	 */
	protected void ConstructBoundingWedge( CurveSegment seg ) {
		if( seg.wedge != null ) {
			PrintMsgLine( "Bounding wedge of "+seg.name+" was already constructed." );
			return;
		}
		// wedge is union of segments? (applies only if curve-segment was not extrapolated)
		if( seg.IsUnion() ) {
			// -> now combine these wedges (construct from union of hodograph vectors)
			//
			// INSERT SOME CURVE-SPECIFIC CODE HERE
			//
			// this code here is only for testing purposes since Bezier-Curves can be extrapolated
			// and this control-path is never executed!
			Point2d[] controls = Point2dSetOps.Concat2( seg.UnionSegL().curve.Controls(), seg.UnionSegR().curve.Controls() );
			seg.wedge = BezierCurve.BoundingWedge( fpMath, controls );
		}
		else {
			seg.wedge = seg.curve.BoundingWedge( fpMath );
		}
		if( this.shapeViewer != null ) {
			seg.shape_wedge = new BoundingWedge2dShape(
				"co_"+seg.name, new Point2df( 0.0, 0.0 ), seg.wedge,
				Color.black, ColorOps.FromArgb( 64, seg.shape_color ),
				true, defFont
			);
		}
		PrintMsgLine( "Bounding wedge of "+seg.name+" constructed." );
	}

	/**
	 * Creates shapes for given state. The shapes are all collected
	 * in the stateShapes-collection
	 * @param state
	 */
	protected void CreateShapes( State state ) {

		if( !stateShapes.containsKey( state ) )
			stateShapes.put( state, new LinkedList<IShape>() );

		LinkedList<IShape> list = stateShapes.get( state );
		BezierCurveShape tempBS;
		float dash1[] = { 10.0f };
		float dash2[] = { 5.0f };

		switch( state ) {

			case Starting:

				try {
					tempBS = new BezierCurveShape( fpMath, "f_orig", f, 64, Color.gray, defFont, false );
					//tempBS.SetCurveStroke( new BasicStroke( 1.0f, BasicStroke.CAP_BUTT, BasicStroke.JOIN_MITER, 10.0f, dash1, 0.0f ) );
					shapeViewer.AddShape( tempBS );
					list.add( tempBS );
					tempBS = new BezierCurveShape( fpMath, "g_orig", g, 64, Color.gray, defFont, false );
					//tempBS.SetCurveStroke( new BasicStroke( 1.0f, BasicStroke.CAP_BUTT, BasicStroke.JOIN_MITER, 5.0f, dash2, 0.0f ) );
					shapeViewer.AddShape( tempBS );
					list.add( tempBS );
					shapeViewer.Flush();
				}
				catch( Exception e ) {
					e.printStackTrace();
				}
				break;

			case AquireNextPair:
				if( cand != null ) {
					shapeViewer.AddShape( cand.fst.seg.shape_curve );
					list.add( cand.fst.seg.shape_curve );
					shapeViewer.AddShape( cand.snd.seg.shape_curve );
					list.add( cand.snd.seg.shape_curve );
					shapeViewer.Flush();
				}
				break;

			case CheckPairHullIntersection:

				if( segPair != null ) {
					if( segPair.fst.shape_curve != null ) {
						shapeViewer.AddShape( segPair.fst.shape_curve );
						list.add( segPair.fst.shape_curve );
					}
					shapeViewer.AddShape( segPair.fst.shape_hull );
					list.add( segPair.fst.shape_hull );
					if( segPair.snd.shape_curve != null ) {
						shapeViewer.AddShape( segPair.snd.shape_curve );
						list.add( segPair.snd.shape_curve );
					}
					shapeViewer.AddShape( segPair.snd.shape_hull );
					list.add( segPair.snd.shape_hull );
					shapeViewer.Flush();
				}
				break;

			case CheckPairBoundingWedgeIntersect:
				if( segPair.fst.shape_wedge != null ) {
					shapeViewer.AddShape( segPair.fst.shape_wedge );
					list.add( segPair.fst.shape_wedge );
				}
				if( segPair.snd.shape_wedge != null ) {
					shapeViewer.AddShape( segPair.snd.shape_wedge );
					list.add( segPair.snd.shape_wedge );
				}
				shapeViewer.Flush();
				break;
		}
	}

	/**
	 * Destroys all shapes of given state
	 * @param state
	 */
	protected void DestroyShapes( State state ) {
		if( !stateShapes.containsKey( state ) )
			return;
		LinkedList<IShape> list = stateShapes.get( state );
		if( list.size() == 0 )
			return;
		for( IShape shape : list ) {
			shapeViewer.RemoveShape( shape );
		}
		shapeViewer.Flush();
		list.clear();
	}

	/**
	 * Returns left sibling node of given one. If domain of sibling will
	 * exceed given domain, <code>null</code> is returned.
	 * If no left sibling node exists in subdivision tree, it is created together
	 * with its parent node. (The grandparent has already be created)
	 * WARNING:
	 * If given node is not the root it is assumed that it is the left child of its parent.
	 * @param node
	 * @param domain
	 * @param firstCurve whether or not the search takes place in subd.-tree of first curve
	 * @return
	 */
	protected SubdivisionNode GetOrCreateLeftSibling( SubdivisionNode node, Interval1d domain, boolean firstCurve ) {
		Interval1d dom = node.seg.domain; // domain of curve segment
		// check whether domain of right sibling is contained in
		// intial curve domain.
		if( !domain.ContainsValue( fpMath.m.subtract( dom.L(), dom.Length() ) ) )
			return null;
		// now that we know that left sibling must be contained in tree, it is
		// contained in a subtree left of given node
		SubdivisionNode p = node.parent; // current node under consideration
		int depth = 1; // depth of given node (starts with 1 here because given node cannot be root)
		while( p.parent.left == p ) {
			p = p.parent;
			depth++;
		}
		depth++;
		// go right down the left sub-tree and eventually create a subtree on the way.
		// A left sub-tree must exist here for two reasons:
		// Firstly otherwise the left sibling would be already outside the initial domain.
		// Secondly it must have been created by subdivision of p.
		p = p.parent.left;
		while( depth > 1 ) {
			if( p.right == null ) { // create subtree?
				SubdivideNode( p, firstCurve );
			}
			p = p.right;
			depth--;
		}
		return p;
	}

	/**
	 * Returns right sibling node of given one. If domain of sibling would
	 * exceed given domain, <code>null</code> is returned.
	 * If no right sibling node exists in subdivision tree, it is created together
	 * with its parent node. (The grandparent has already be created)
	 * WARNING:
	 * If given node is not the root it is assumed that it is the right child of its parent.
	 * @param node
	 * @param domain
	 * @param firstCurve whether or not the search takes place in subd.-tree of first curve
	 * @return
	 */
	protected SubdivisionNode GetOrCreateRightSibling( SubdivisionNode node, Interval1d domain, boolean firstCurve ) {
		Interval1d dom = node.seg.domain; // domain of curve segment
		// check whether domain of right sibling is contained in
		// intial curve domain.
		if( !domain.ContainsValue( fpMath.m.add( dom.U(), dom.Length() ) ) )
			return null;
		// now that we know that right sibling must be contained in tree, it is
		// contained in a subtree right of given node
		SubdivisionNode p = node.parent; // current node under consideration
		int depth = 1; // depth of given node (starts with 1 here because given node cannot be root)
		while( p.parent.right == p ) {
			p = p.parent;
			depth++;
		}
		depth++;
		// go left down the right sub-tree and eventually create subtree on the way
		// a right sub-tree must exist here otherwise the right sibling would
		// be already outside the initial domain.
		p = p.parent.right; // right sub-tree must exist here because it was create by subdivision of p
		while( depth > 1 ) {
			if( p.left == null ) { // create subtree?
				SubdivideNode( p, firstCurve );
			}
			p = p.left;
			depth--;
		}
		return p;
	}

	/**
	 * Initializes member variables
	 */
	private void InitializeMembers() {
		this.shapeViewer = null;
		this.stackList = null;
		this.messageBox = null;
		this.fRoot = null;
		this.gRoot = null;
		this.treshold = null;
		this.fpMath = null;
		this.parameters = 0;
		this.statistics = null;
		this.maxDepth_f = 0;
		this.maxDepth_g = 0;
		this.currentPrecision = 0;
		this.startPrecision = 0;
		
		this.intersections = null;

		this.macroPairs = null;
		this.microPairs = null;

		this.deltaYap = null;
		this.L = 0;

    this.stack = new Stack<Tuple2<SubdivisionNode,SubdivisionNode>>();
		this.stateShapes = new HashMap<State, LinkedList<IShape>>();

    this.spSegPairs2Check = new LinkedList<Tuple2<CurveSegment,CurveSegment>>();
		
		this.segPair = null;
		this.defFont = null;
	}

	/**
	 * Returns whether given segment pair (s1,s2) was already checked.
	 * @param s1
	 * @param s2
	 * @return
	 */
	protected boolean IsSegmentPairAlreadyChecked( CurveSegment s1, CurveSegment s2 ) {
		return (s1.IsAlreadyChecked( s2.domain ) || s2.IsAlreadyChecked( s1.domain ));
	}

	/**
	 * Returns name for given segment pair
	 * @param f
	 * @param g
	 * @return
	 */
	protected static String NameOfSegPair( CurveSegment f, CurveSegment g ) {
		return "("+f.name+", "+g.name+")";
	}

	/**
	 * Prints given message to log
	 * @param msg
	 */
	protected void PrintMsg( String msg ) {
		if( (parameters & Parameters.LOG) != 0 && messageBox != null )
			messageBox.append( msg );
	}

	/**
	 * Prints given message together with a line break to log
	 * @param msg
	 */
	protected void PrintMsgLine() {
		if( (parameters & Parameters.LOG) != 0 && messageBox != null )
			messageBox.append( "\n" );
	}

	/**
	 * Prints given message together with a line break to log
	 * @param msg
	 */
	protected void PrintMsgLine( String msg ) {
		if( (parameters & Parameters.LOG) != 0 && messageBox != null )
			messageBox.append( msg+"\n" );
	}

	/**
	 * Resets algorithm members so that algorithm is in starting state.
	 */
	protected void ResetMembers() {
		this.intersections = new LinkedList<Intersection>();
		this.macroPairs = new LinkedList<Tuple2<Interval1d, Interval1d>>();
		this.microPairs = new LinkedList<Tuple2<Interval1d, Interval1d>>();
		
		// set initial precision to double-precision (16 decimal places)
		startPrecision = 48;
		currentPrecision = startPrecision;
		fpMath = new FPMath( startPrecision );
		maxDepth_f = 0;
		maxDepth_g = 0;
		// start statistics
		if( (parameters & Parameters.COLLECT_DATA) != 0 ) {
			statistics = new Statistics();
			statistics.startPrecision = startPrecision;
		}
		// calculate yap separation bounds?
		if( (parameters & Parameters.BOUNDS_YAP) != 0 ) {
			deltaYap = YapUtilities.CalculateMaxSquareDelta( L, f.Degree(), g.Degree() );
		}
		squareTreshold = treshold.multiply( treshold );
		currentState = State.Starting;
		nextState = State.AquireNextPair;
		segPair = null;
		spSegPairs2Check.clear();
		cand = null;
    oneSCMPPairDisjoint = false;
		intersections.clear();
		stack.clear();
		if( stackList != null )
			stackList.clear();
		if( shapeViewer != null )
			shapeViewer.Clear();
		stateShapes.clear();

		PrintMsg( "\n=====================\nStarting\n=====================\n\n" );

		if( f.IsDegenerated() || g.IsDegenerated() ) {
			if( f.Controls()[0].Equals( g.Controls()[0] ) ) {
				AddIntersection( f.Domain(), g.Domain(), IntersectionType.Unique );
			}
			return;
		}

		// original curves
		if( this.shapeViewer != null ) {
			CreateShapes( State.Starting );
		}

		CurveSegment fs = null, gs = null;
		try {
			BezierCurveShape fShape = null;
			BezierCurveShape gShape = null;
			if( this.shapeViewer != null ) {
				fShape = new BezierCurveShape( fpMath, "f", f, 64, shape_color_f, defFont, false );
				gShape = new BezierCurveShape( fpMath, "g", g, 64, shape_color_g, defFont, false );
			}
			fs = new CurveSegment( f, fShape );
			gs = new CurveSegment( g, gShape );
		}
		catch( Exception e ) {
			e.printStackTrace();
			return;
		}
		
		fRoot = new SubdivisionNode( fs, null, null, null );
		gRoot = new SubdivisionNode( gs, null, null, null );
		stack.push( new Tuple2<SubdivisionNode,SubdivisionNode>( fRoot, gRoot ) );
		// first segment pair
		if( stackList != null )
			stackList.add( 0, "{ "+fs.name+", "+gs.name+" }" );
	}

	/**
	 * Subdivides given node of subdivision tree.
	 * @param node
	 * @param firstCurve whether or not node belongs to subdivision tree of first curve
	 */
	protected void SubdivideNode( SubdivisionNode node, boolean firstCurve ) {
		// keep track of maximal subdivision depth
		// eventually increase precision by 1 (one bit per subdivision) if a new
		// subdivision level was reached
		if( firstCurve ) {
			maxDepth_f = Math.max( node.depth+1, maxDepth_f );
			if( currentPrecision-startPrecision < maxDepth_f ) {
				currentPrecision++;
				this.fpMath.SetPrecision( currentPrecision );
			}
			if( (parameters & Parameters.COLLECT_DATA) != 0 ) {
				statistics.numSubdivisions_f++;
			}
		}
		else {
			maxDepth_g = Math.max( node.depth+1, maxDepth_g );
			if( currentPrecision-startPrecision < maxDepth_g ) {
				currentPrecision++;
				this.fpMath.SetPrecision( currentPrecision );
			}
			if( (parameters & Parameters.COLLECT_DATA) != 0 ) {
				statistics.numSubdivisions_g++;
			}
		}
		// now subdivide
		Tuple2<BezierCurve, BezierCurve> subc;
		try {
			subc = node.seg.curve.Subdivide( fpMath, fpMath._0_5 );
			BezierCurveShape ls = null, rs = null;
			if( this.shapeViewer != null ) {
				ls = new BezierCurveShape( fpMath, node.seg.name+"0", subc.fst, 64, node.seg.shape_curve.Color(), defFont, false );
				rs = new BezierCurveShape( fpMath, node.seg.name+"1", subc.snd, 64, node.seg.shape_curve.Color(), defFont, false );
			}
			node.left = new SubdivisionNode( new CurveSegment( subc.fst, ls ), node, null, null );
			node.right = new SubdivisionNode( new CurveSegment( subc.snd, rs ), node, null, null );
			node.left.depth = node.right.depth = node.depth+1;
		}
		catch( Exception e ) {
			e.printStackTrace();
		}
	}
	
	//
	// STATICSTICAL METHODS
	//

	/**
	 * Method calculates several mean values based on subdivision trees
	 * of current input curves.
	 * The values are stored in the statistics data object
	 */
	protected void CalculateSubdivsionTreeMeans() {
		if( fRoot == null )
			return;
		// traverse subdivision trees in dfs order
		Stack<SubdivisionNode> st = new Stack<SubdivisionNode>();
		SubdivisionNode n = null;
		// for f
		st.push( fRoot );
		statistics.minComparedIntervals_f = Integer.MAX_VALUE;
		statistics.maxComparedIntervals_f = 0;
		statistics.numNodes_f = 0;
		double sum = 0.0;
		int numSegments = 0;
		while( st.size() > 0 ) {
			n = st.pop();
			numSegments = n.seg.CountCheckedSegments();
			statistics.numNodes_f++;
			sum += numSegments;
			statistics.minComparedIntervals_f = Math.min( statistics.minComparedIntervals_f, numSegments );
			statistics.maxComparedIntervals_f = Math.max( statistics.maxComparedIntervals_f, numSegments );
			if( n.left != null ) st.push( n.left );
			if( n.right != null ) st.push( n.right );
		}
		statistics.meanComparedIntervals_f = sum/(double)statistics.numNodes_f;
		// for g
		st.push( gRoot );
		statistics.minComparedIntervals_g = Integer.MAX_VALUE;
		statistics.maxComparedIntervals_g = 0;
		statistics.numNodes_g = 0;
		sum = 0.0;
		while( st.size() > 0 ) {
			n = st.pop();
			numSegments = n.seg.CountCheckedSegments();
			statistics.numNodes_g++;
			sum += numSegments;
			statistics.minComparedIntervals_g = Math.min( statistics.minComparedIntervals_g, numSegments );
			statistics.maxComparedIntervals_g = Math.max( statistics.maxComparedIntervals_g, numSegments );
			if( n.left != null ) st.push( n.left );
			if( n.right != null ) st.push( n.right );
		}
		statistics.meanComparedIntervals_g = sum/(double)statistics.numNodes_g;
	}

	//
	// MEMBERS
	//

	/**
	 * current state of algorithm
	 */
	private State currentState;
	/**
	 * next state of algorithm
	 */
	private State nextState;
	/**
	 * collection storing algorithm shapes
	 */
	private ShapeViewer shapeViewer;
	/**
	 * list displaying current candidate stack
	 */
	private DefaultListModel stackList;
	/**
	 * box displaying algorithm log
	 */
	private JTextArea messageBox;
	/**
	 * one of the curves
	 */
	private BezierCurve f;
	/**
	 * one of the input curves
	 */
	private BezierCurve g;
	/**
	 * "size" of first input curve
	 */
	private Apfloat size_f;
	/**
	 * "size" of second input curve
	 */
	private Apfloat size_g;
	/**
	 * root of subdivision-tree for one of the curves
	 */
	private SubdivisionNode fRoot;
	/**
	 * root of subdivision-tree for one of the curves
	 */
	private SubdivisionNode gRoot;
	/**
	 * Current candidate pair
	 */
	private Tuple2<SubdivisionNode,SubdivisionNode> cand;
	/**
	 * stack containing subdivision node pairs
	 */
	private Stack<Tuple2<SubdivisionNode,SubdivisionNode>> stack;
	/**
	 * list of supercomposition segment pairs to check
	 */
	private LinkedList<Tuple2<CurveSegment,CurveSegment>> spSegPairs2Check;
	/**
	 * current segment pair under consideration
	 */
	private Tuple2<CurveSegment,CurveSegment> segPair;
	/**
	 * shapes describing current state
	 */
	private HashMap<State,LinkedList<IShape>> stateShapes;
	/**
	 * macro-pairs found
	 */
	private LinkedList<Tuple2<Interval1d,Interval1d>> macroPairs;
	/**
	 * micro-pairs found
	 */
	private LinkedList<Tuple2<Interval1d,Interval1d>> microPairs;
	/**
	 * list of intersections found
	 */
	private LinkedList<Intersection> intersections;
	/**
	 * base color of first input curve's shapes
	 */
	Color shape_color_f;
	/**
	 * base color of second input curve's shapes
	 */
	Color shape_color_g;
	/**
	 * default drawing font
	 */
	private Font defFont;
	/**
	 * Treshold value to be specified by calling application.
	 * Algorithm stops if length of curve segments run below this value.
	 */
	private Apfloat treshold;
	/**
	 * square of treshold
	 */
	private Apfloat squareTreshold;
	/**
	 * Fixed (but arbitrary) precision math object
	 */
	private FPMath fpMath;
	/**
	 * starting precision
	 */
	private int startPrecision;
	/**
	 * current precision
	 */
	private int currentPrecision;
	/**
	 * maximum depth of a subdivision node for first curve
	 */
	private int maxDepth_f;
	/**
	 * maximum depth of a subdivision node for second curve
	 */
	private int maxDepth_g;
	/**
	 * Statistic data
	 */
	private Statistics statistics;
	/**
	 * parameters controlling algorithm behaviour
	 */
	private int parameters;
	/**
	 * yap delta
	 */
	private Apfloat deltaYap;
	/**
	 * L-bit float bits
	 */
	private int L;
  /**
   * one of the scmp-pairs was disjoint?
   */
  private boolean oneSCMPPairDisjoint;
}
